public class Test {
    //返回两个链表的相交节点
    public MysingleList.Node getIntersectionNode(MysingleList.Node headA, MysingleList.Node headB) {
        //求两个链表长度
        int lenA=0;
        int lenB=0;
        MysingleList.Node pl=headA;
        MysingleList.Node ps=headB;//假设headB比较短
        while(pl!=null){
            pl=pl.next;
            lenA++;
        }
        while(ps!=null){
            ps=ps.next;
            lenB++;
        }
        //pl和ps用完重新指向headA和headB
        pl=headA;
        ps=headB;
        int len=lenA-lenB;
        if(lenA<0){//说明headA比headB短，交换
            pl=headB;
            ps=headA;
        }
        //较长的链表先动len步
        while (len!=0){
            pl=pl.next;
            len--;
        }
        while(pl!=ps){
            //没找到相交节点时,继续移动
            pl=pl.next;
            ps=ps.next;
        }
        //找到相等节点,即使两个都为null也返回
        return pl;
    }
    //合并两个有序链表
    public static MysingleList.Node mergeTwoLists(MysingleList.Node head1, MysingleList.Node head2) {
        MysingleList.Node newhead=new MysingleList.Node(0) ;
        MysingleList.Node tmp=newhead;
        while(head1!=null&&head2!=null){
            if (head1.val>head2.val){
                tmp.next=head2;
                head2=head2.next;
                tmp=tmp.next;
            }else{
                tmp.next=head1;//形成指向
                head1=head1.next;
                tmp=tmp.next;
            }
        }
        if (head1!=null){
            tmp.next=head1;
        } else if (head2!=null) {
            tmp.next=head2;
        }
        return newhead.next;
    }

    public static void main(String[] args) {
        MysingleList mysingleList=new MysingleList();
        mysingleList.addLast(1);
        mysingleList.addLast(2);
        mysingleList.addLast(3);
        mysingleList.addLast(4);
        mysingleList.display3(mysingleList.head);//递归打印
        System.out.println("__________________");
        MysingleList mysingleList1=new MysingleList();
        mysingleList1.addLast(11);
        mysingleList1.addLast(22);
        mysingleList1.addLast(33);
        mysingleList1.addLast(44);
        mysingleList1.display4();
    }
    public static void main1(String[] args) {
        System.out.println("++++++++++++++++++++");
        MysingleList mysingleList1=new MysingleList();
        mysingleList1.addLast(12);
        mysingleList1.addLast(14);
        mysingleList1.addLast(16);
        mysingleList1.addLast(18);
        mysingleList1.display();
        System.out.println("++++++++++++++");

        MysingleList mysingleList2=new MysingleList();
        mysingleList2.addLast(13);
        mysingleList2.addLast(15);
        mysingleList2.addLast(17);
        mysingleList2.addLast(19);
        mysingleList2.display();
        System.out.println("+++++++++++++");

        MysingleList.Node ret=mergeTwoLists(mysingleList1.head,mysingleList2.head);
        mysingleList1.display(ret);
    }
    public static void main9(String[] args) {
        MysingleList mysingleList=new MysingleList();
        mysingleList.createLink();//创建链表
        mysingleList.display();//展示
        System.out.println(mysingleList.contains(100));//判断是否含有100
        System.out.println(mysingleList.size());//计算链表个数
        System.out.println("_________________-");
        mysingleList.addIndex(4,99);//在指定位置插入值
        mysingleList.display();//展示
        System.out.println("_________________");
       /* mysingleList.reverseList();//链表反转
        mysingleList.display();*/
        mysingleList.display();
        MysingleList.Node ret=mysingleList.findKthTotail(2);
        System.out.println(ret);
    }
}
